\section{排列}

\begin{frame}{排列}
作为定义 $n$ 阶行列式的准备，我们先来讨论一下排列的性质。

\begin{definition}%定义1 
  由 $1,2, \cdots, n$ 组成的一个有序数组称为一个 \emph{$n$ 阶排列}。
\end{definition}
\pause
例如， $2431$ 是一个 $4$ 阶排列， $45321$ 是一个 $5$ 阶排列。 我们知道， $n$ 阶排列的总数是
\[
n \cdot(n-1) \cdot(n-2) \cdot \cdots \cdot 2 \cdot 1
\]
\pause
我们记
\[
1 \cdot 2 \cdot \cdots \cdot(n-1) \cdot n=n !,
\]
读为 ``$n$ 阶乘''. 例如： $4 !=4 \times 3 \times 2 \times 1=24$, $5 !=120$. $n!$ 随着 $n$ 的增大迅速地增大。 例如， $10!=3628800$.

\end{frame}

\begin{frame}{排列的奇偶性（符号）}
显然 $12 \cdots n$ 也是一个 $n$ 阶排列。 这个排列是按照递增的顺序排起来的， 称为自然顺序，其他的排列都或多或少地破坏自然顺序。

\begin{definition}%定义2 
  在一个排列中， 如果一对数的前后位置与大小顺序相反， 即前面的数大于后面的数， 那么它们就称为一个\emph{逆序}， 一个排列中逆序的总数就称为这个排列的\emph{逆序数}。
排列 $j_{1} j_{2} \cdots j_{n}$ 的逆序数记为
$\tau\left(j_{1} j_{2} \cdots j_{n}\right)$.
\end{definition}
\pause
例如 $2431$ 中， $21,43,41,31$ 是逆序， $2431$ 的逆序数就是 $4$. 而 $45321$ 的逆序数是 $9$.
\pause
  \begin{definition}%定义3 
    逆序数为偶数的排列称为\emph{偶排列}， 逆序数为奇数的排列称为\emph{奇排列}。
    对排列$j_1j_2\cdots j_n$, $(-1)^{\tau(j_1j_2\ldots j_n)}$称为该排列的\emph{符号}。这样
    偶排列相当于符号为$+$的排列，而奇排列相当于符号为$-$的排列。
\end{definition}

例如， $2431$ 是偶排列， $45321$ 是奇排列， $12 \cdots n$ 的逆序数是零，因之是偶排列。

\pause
应该指出， 我们同样可以考虑由任意 $n$ 个不同的自然数所组成的排列， 一般地也称为 \emph{$n$ 阶排列}。 
对这样一般的 $n$ 阶排列， 同样可以定义上面这些概念。

\pause
把一个排列中某两个数的位置互换， 而其余的数不动， 就得到另一个排列。 
这样一个变换称为一个\emph{对换}。 
\pause
例如， 经过 $1,2$ 对换，排列 $2431$ 就变成了 $1432$,
排列 $2134$ 就变成了 $1234$. 
\pause
显然， 如果连续施行两次相同的对换， 那么排列就还原了。 
由此得知， 一个对换把全部 $n$ 阶排列两两配对，使每两个配成对的 $n$ 阶排列在这个对换下互变。
\end{frame}

\begin{frame}
关于排列的奇偶性，我们有下面的基本事实。


\begin{theorem}%定理1 
对换改变排列的奇偶性。
\end{theorem}
也就是说，经过一次对换，奇排列变成偶排列，偶排列变成奇排列。

\pause
\begin{proof}
我们来数下一次对换后排列的逆序数的变化量是多少。
      设对换了排列中的数字$a,b$. 
      记$a, b$之间的数字构成的集合为$I$, $a$左边的构成的集合为$I'$, 
      $b$右边的构成的集合为$I''$（图示一下！）。 
      考虑任一对不同的数字$i, j$. 
  若对换$a, b$后$i, j$的相对位置未变，则其对逆序数的变化量的贡献是$0$;
  若$i,j$从顺序变成逆序，则其对逆序数的变化量的贡献是$1$;
  若$i,j$从逆序变成顺序，则其对逆序数的变化量的贡献是$-1$.
  下面我们对所有不同的互异数字$i,j$统计总的变化量。
  为了避免重复，我们总设对换前$i$在$j$左边。
  下列情形时$i, j$在对换后的相对位置未变：
  (i) $i\in I', j$任意 (在$i$右边)；(ii) $j\in I''$, $i$任意 (在$j$左边)；(iii) $i, j\in I$. 
  所以这些情形对逆序数的变化的贡献是$0$.
  剩下的情形是：(iv) $i=a, j\in I$; (v) $i=a, j=b$; (vi) $i\in I, j=b$.
  设排列中$a, b$之间有$m$个数字（即$\sharp I=m$）, 其中比$a$小的有$k$个（比$a$大的就有$m-k$个），
  其中比$b$大的有$l$个（比$b$小的就有$m-l$个）。
  对换$a,b$后，情形(iv) 对逆序数的变化量的贡献是$(m-k)-k$, (v)的是$\pm 1$, (vi)的是$(m-l)-l$. 
  总变化量是
  \[
    (m-k)-k+(m-l)-l\pm 1=2(m-k-l)\pm 1,
  \]
  是奇数。如此，若对换前逆序数为奇数 (转：偶数)，对换后逆序数为偶数 (转：奇数)。
因此排列的奇偶性在一次对换后改变。
\end{proof}
%\begin{proof}
%先看一个特殊的情形，即对换的两个数在排列中是相邻的情形。排列
%\begin{equation*}
%\cdots j k \cdots \tag{1}
%\end{equation*}
%经过 $j, k$ 对换变成
%\begin{equation*}
%\cdots k j \cdots \tag{2}
%\end{equation*}
%这里“...”表示那些不动的数。显然， 在排列 (1) 中如 $j, k$ 与其他的数构成逆序， 
%则在排列 (2) 中仍然构成逆序; 如不构成逆序则在 (2) 中也不构成逆序; 
%不同的只是 $j, k$ 的次序。 如果原来 $j, k$ 组成逆序， 那么经过对换， 逆序数就减少一个; 
%如果原来 $j, k$ 不组成逆序， 那么经过对换， 逆序数就增加一个。 
%不论增加 $1$ 还是减少 $1$, 排列的逆序数的奇偶性总是变了。因之，在这个特殊的情形，定理是对的。
%
%再看一般的情形。 设排列为
%\begin{equation*}
%\cdots j i_{1} i_{2} \cdots i_{s} k \cdots \tag{3}
%\end{equation*}
%经过 $j, k$ 对换，排列 (3)变成
%\begin{equation*}
%\cdots k i_{1} i_{2} \cdots i_{s} j \cdots \tag{4}
%\end{equation*}
%不难看出，这样一个对换可以通过一系列的相邻数的对换来实现。 从 (3) 出发，把 $k$与 $i_{s}$ 对换，再与 $i_{s-1}$ 对换……也就是说，把 $k$ 一位一位地向左移动。 经过 $s+1$ 次相邻位置的对换，排列 (3) 就变成
%\begin{equation*}
%\cdots k j i_{1} i_{2} \cdots i_{s} \cdots \tag{5}
%\end{equation*}
%从 (5) 出发，再把 $j$ 一位一位地向右移动， 经过 $s$ 次相邻位置的对换， 排列 (5) 就变成了排列 (4). 因之， $j, k$ 对换可以通过 $2 s+1$ 次相邻位置的对换来实现 $2 s+1$ 是奇数。 相邻位置的对换改变排列的奇偶性。显然，奇数次这样的对换的最终结果还是改变奇偶性。 
%\end{proof}

\end{frame}

\begin{frame}
根据定理 1 ,可以证明以下重要结论。


\begin{corollary}%推论 
  在全部 $n$ (其中$n>1$) 阶排列中，奇、偶排列的个数相等，各有 $n ! / 2$ 个。
\end{corollary}

\pause

\begin{proof}
假设在全部 $n$ 阶排列中共有 $s$ 个奇排列， $t$ 个偶排列。
将 $s$ 个奇排列中的前两个数字对换， 得到 $s$ 个不同的偶排列， 因此 $s \leqslant t$. 
同样可证 $t$ $\leqslant s$,于是 $s=t$, 即奇、偶排列的总数相等， 各有 $n ! / 2$ 个。 
\end{proof}


\pause
\begin{theorem}%定理2 
  \label{10F}
任意一个 $n$ 阶排列与排列 $12 \cdots n$ 都可以经过一系列对换互变， 并且所作对换的个数与这个排列有相同的奇偶性。
\end{theorem}



%\begin{proof}
%我们对排列的阶数 $n$ 作数学归纳法， 来证任意一个 $n$ 阶排列都可以经过一系列对换变成 $12 \cdots n$.
%$1$ 阶排列只有一个，结论显然成立。
%假设结论对 $n-1$ 阶排列已经成立，现在来证对 $n$ 阶排列的情形结论也成立。
%设 $j_{1} j_{2} \cdots j_{n}$ 是一个 $n$ 阶排列，如果 $j_{n}=n$, 那么根据归纳法假设， 
%$n-1$ 阶排列 $j_{1} j_{2} \cdots j_{n-1}$可以经过一系列对换变成 $12 \cdots(n-1)$,
%于是这一系列对换也就把 $j_{1} j_{2} \cdots j_{n}$ 变成 $12 \cdots n$.
%如果 $j_{n} \neq n$, 那么对 $j_{1} j_{2} \cdots j_{n}$ 作 $j_{n}, n$ 对换，
%它就变成 $j_{1}^{\prime} \cdots j_{n-1}^{\prime} n$, 这就归结成上面的情形， 因此结论普遍成立。
%相仿地， $12 \cdots n$ 也可用一系列对换变成 $j_{1} j_{2} \cdots j_{n}$, 因为 $12 \cdots n$ 是偶排列， 
%所以根据定理 1 ,所作对换的个数与排列 $j_{1} j_{2} \cdots j_{n}$ 有相同的奇偶性。 
%\end{proof}
\pause
\begin{proof}[通过例子说明]
  考虑自然排列$12\cdots n$. 若$1\neq i_1$, 对换排列中的$1$与$i_1$; 
  若$2\neq i_2$, 再对换$2$与$i_2$; 
  如此进行下去，最终我们通过一些对换得到$i_1i_2\cdots i_n$. 
  显然对换可逆，且其逆操作还是这个对换，
  从而我们也可从$i_1i_2\cdots i_n$出发不断地对换变回自然排列。
  由于$12\cdots n$是偶排列，而对换改变排列的奇偶性，
  故不断对换得到的排列$i_1i_2\cdots i_n$的奇偶性与对换次数的奇偶性相同。
\end{proof}

\end{frame}


\begin{frame}
  \begin{example}
  %写出所有的$4$阶奇排列和偶排列。
  %我们知道任何一个$n$阶排列都可由自然排列
   % $12\cdots n$做一系列对换得到，而且对换改变排列的奇偶性，
    %这样我们可以追踪到每个排列的奇偶性。
    如下的一系列对换我们得到了所有$4$阶排列（$4!=24$个）：
    \[
      \begin{tikzcd}[column sep=small, row sep=small, ampersand replacement=\&]
        1234\ar[r]\ar[d]  \& 1243 \ar[r] \ar[d] \& 1342 \ar[d] \ar[r] \& 
        1324 \ar[r] \ar[d] \& 1423 \ar[r] \ar[d] \& 1432  \ar[d] \\
        2134 \ar[d] \& 2143 \ar[d] \& 2341 \ar[d] \& 2314 \ar[d] \& 2413  \ar[d]
        \& 2431 \ar[d] \\
        3124 \ar[d] \& 3142 \ar[d] \& 3241 \ar[d] \& 3214 \ar[d] \& 3412\ar[d] \&  3421\ar[d]  \\
        4123 \& 4132 \& 4231 \& 4213 \& 4312 \& 4321.
      \end{tikzcd}
    \]
    \pause
  奇偶性变化为
  \[
    \begin{tikzcd}[column sep=small, row sep=small, ampersand replacement=\&]
      \text{偶} \ar[r]\ar[d] \& \text{奇} \ar[r]\ar[d] \& \text{偶} \ar[r]\ar[d] \& 
      \text{奇}  \ar[r]\ar[d] \& \text{偶} \ar[r]\ar[d] \& \text{奇} \ar[d] \\
      \text{奇} \ar[d] \& \text{偶} \ar[d] \& \text{奇}  \ar[d] \& 
      \text{偶} \ar[d] \& \text{奇} \ar[d] \& \text{偶}\ar[d] \\
      \text{偶} \ar[d] \& \text{奇} \ar[d] \& \text{偶} \ar[d] \& 
      \text{奇} \ar[d]  \& \text{偶} \ar[d] \& \text{奇} \ar[d] \\
      \text{奇} \& \text{偶} \& \text{奇}  \& \text{偶} \& \text{奇} \& \text{偶}.
    \end{tikzcd}
  \]
  \pause
  所以所有$12$个$4$阶偶排列和所有$12$个$4$阶奇排列分别为
  \[
  \begin{aligned}
      1234, 1342, 1423, 2143, 2314, 2431, 3124, 3241, 3412, 4132, 4213, 4321;\\
        1243,1324,1432, 2134, 2341, 2413, 3142, 3214, 3421, 4123, 4231, 4312.
      \end{aligned}
\]
\end{example}
\end{frame}


\begin{frame}{小结}

  \begin{enumerate}
    \item 何为$n$阶排列？总共有多少个？奇排列、偶排列各多少个？
    \item 何为排列中的逆序、顺序？何为逆序数？
    \item 何为排列的奇偶性？何为排列的符号？
    \item 何为对换？对换对排列的奇偶性 (或符号) 的效果是？
    \item 给定一个排列，如何通过不断对换实现其与自然排列的互变？
      对换的次数的奇偶性与所给排列的奇偶性关系如何？
  \end{enumerate}
  

\end{frame}
